#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites)
    {
        vector<vector<int>> egdes(n);
        vector<int> in(n);
        queue<int> q;
        for (auto e : prerequisites)
        {
            //e[1] -> e[0]
            egdes[e[1]].push_back(e[0]);
            in[e[0]]++;
        }

        for (int i = 0; i < n; i++)
        {
            if (in[i] == 0) q.push(i);
        }

        while (q.size())
        {
            int sz = q.size();
            while (sz--)
            {
                int front = q.front();
                q.pop();
                for (auto e : egdes[front])
                {
                    in[e]--;
                    if (in[e] == 0) q.push(e);
                }
            }
        }

        for (int i = 0; i < n; i++)
        {
            if (in[i] != 0) return false;
        }

        return true;
    }
};

class Solution
{
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int ret = 0;
    int m, n;
    vector<vector<bool>> vis;
public:
    int orangesRotting(vector<vector<int>>& grid)
    {
        queue<pair<int, int>> q;
        m = grid.size(), n = grid[0].size();
        vis = vector<vector<bool>>(m, vector<bool>(n));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 2) q.push({ i, j });
            }
        }

        while (q.size())
        {
            int sz = q.size();
            ret++;
            while (sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for (int i = 0; i < 4; i++)
                {
                    int x = a + dx[i];
                    int y = b + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
                    {
                        vis[x][y] = true;
                        q.push({ x, y });
                    }
                }
            }
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1 && !vis[i][j]) return -1;
            }
        }

        return ret == 0 ? 0 : ret - 1;
    }
};
class Solution
{
    int ret = INT_MIN;
public:
    int dfs(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int leftsum = dfs(root->left);
        int rightsum = dfs(root->right);
        ret = max(ret, root->val + max(0, leftsum) + max(0, rightsum));
        return max(0, root->val + max(leftsum, rightsum));
    }
    int maxPathSum(TreeNode* root)
    {
        dfs(root);
        return ret;
    }
};
class Solution
{
public:
    bool dfs(TreeNode* root, TreeNode* target, stack<TreeNode*>& st)
    {
        if (root == nullptr) return false;
        st.push(root);
        if (target == root) return true;
        bool left = dfs(root->left, target, st);
        if (left) return true;
        bool right = dfs(root->right, target, st);
        if (right) return true;
        st.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        stack<TreeNode*> st1;
        stack<TreeNode*> st2;
        dfs(root, p, st1);
        dfs(root, q, st2);

        int sz1 = st1.size();
        int sz2 = st2.size();

        int diff = abs(sz1 - sz2);
        if (sz1 > sz2)
        {
            while (diff--) st1.pop();
        }
        else
        {
            while (diff--) st2.pop();
        }

        while (st1.top() != st2.top())
        {
            st1.pop();
            st2.pop();
        }

        return st1.top();
    }
};
class Solution
{
    long long path = 0;
    unordered_map<long long, int> hash;
    int target;
    int ret = 0;
public:
    void dfs(TreeNode* root)
    {
        if (root == nullptr) return;
        path += root->val;
        if (hash[path - target]) ret += hash[path - target];
        hash[path]++;
        dfs(root->left);
        dfs(root->right);
        hash[path]--;
        path -= root->val;
    }
    int pathSum(TreeNode* root, int targetSum)
    {
        hash[0] = 1;
        target = targetSum;
        dfs(root);
        return ret;
    }
};
class Solution
{
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int inbegin, int inend, int& previ)
    {
        if (inbegin > inend) return nullptr;
        int rooti = 0;
        for (int i = inbegin; i <= inend; i++)
        {
            if (inorder[i] == preorder[previ])
            {
                rooti = i;
                break;
            }
        }
        previ++;
        TreeNode* root = new TreeNode(inorder[rooti]);
        root->left = _buildTree(preorder, inorder, inbegin, rooti - 1, previ);
        root->right = _buildTree(preorder, inorder, rooti + 1, inend, previ);

        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int previ = 0;
        return _buildTree(preorder, inorder, 0, inorder.size() - 1, previ);
    }
};
class Solution {
public:
    void flatten(TreeNode* root)
    {
        _flatten(root);
    }

    TreeNode* _flatten(TreeNode* root)
    {
        if (root == nullptr) return nullptr;
        TreeNode* right = _flatten(root->right);
        TreeNode* left = _flatten(root->left);

        root->left = nullptr;
        root->right = left;
        TreeNode* cur = root;
        while (cur->right) cur = cur->right;
        cur->right = right;

        return root;
    }
};

